Papers^γ

### Very nice associated website: http://web.stanford.edu/~montanar/SDPgraph/ Slides: http://www.lps.ens.fr/~krzakala/LESHOUCHES2017/talks/LesHouches2017_RicciTersenghi.pdf ### Generalising to the Goemans-Williamson algorithm: Can we implement the Goemans-Williamson algorithm using this "spin technique"? This is a try: https://github.com/maxdan94/spingraphSDP I think that it may be interesting as it could lead to a scalable implementation of the Goemans-Williamson algorithm. ### Minors: - In the main text, some equation numbers correspond to the equations in the supplementary material, e.g. "(42)", "(49)" or "(288)". This makes the paper hard to read. "(288)" should be replaced by "(10)". - "solving the combinatorial optimization problem in Eq. (5) is a prototypical NP-complete problem." This is not a decision problem and thus it cannot be NP-complete by definition. - "(total CPU time was about 10 years)" This is not clear: what does it mean exactly? Which type of machines were used?

### Wrong reference: I read "It is also known that, for $m >\sqrt{2 n}$, the problem (49) has no local optima except the global ones [BM03]." In [BM03], which is [this paper](https://papers-gamma.link/paper/55), there is no such proof! We can only read: "Theorem 2.2. There exists an optimal solution $X^∗$ of (1) with rank r satisfying the inequality $r(r+ 1)/2 ≤ m$." and "we present computational results which show that the method finds optimal solutions to (2) quite reliably, and although we are able to derive some amount of theoretical justification for this, our belief that the method is not strongly affected by the inherent nonconvexity of (2) is largely experimental" but not that any local minimum is a global minimum.

> ### Minors: > > - "(total CPU time was about 10 years)" This is not clear: what does it mean exactly? Which type of machines were used? Although the algorithm based on the minimization of a non-convex cost function in terms of m-component variables is extremely fast to solve a single SBM problem (see e.g. figure 5 in https://arxiv.org/pdf/1603.09045, where many numerical experiments are reported) the precise determination of the critical threshold in the sparse case (i.e. SBM) required a large numerical effort of more than 80,000 core hours (we run all out simulations on Intel(R) Xeon(R) CPU E5-2670 @ 2.60GHz).